package net.zjitc.tree.linked;

public class BTree {
    TreeNode<Integer> root;

    public void add(Integer value) {
        //根节点
        if (root == null) {
            root = new TreeNode<>(value);
            return;
        }
        //插入？相比较（每次都是从根比较），再插入（一定是没有孩子才能插入）
        //每次都是从根进行比较
        TreeNode<Integer> currentNode = root;
        //比较
        while (true) {//规则
            if (value < currentNode.data) {//值比当前值小 插入左边
                if (currentNode.left == null) {
                    currentNode.left = new TreeNode<>(value);
                    return;
                }
                currentNode = currentNode.left;
            } else if (value > currentNode.data) {//值比当前值大 插入右边
                if (currentNode.right == null) {
                    currentNode.right = new TreeNode<>(value);
                    return;
                }
                currentNode = currentNode.right;
            } else {
                return;
            }

        }
    }

    /**
     * 树中是否存在此值
     *
     * @param key
     * @return
     */
    public boolean search(int key) {
        TreeNode<Integer> currentNode = root;
        while (true) {
            if (currentNode == null) {
                return false;
            }
            if (currentNode.data == key) {
                return true;
            }
            if (currentNode.data > key) {
                currentNode = currentNode.right;
            }
            if (currentNode.data < key) {
                currentNode = currentNode.left;
            }
        }
    }

    /**
     * 另一种方法（递归）
     * @return
     */
    public boolean find(TreeNode<Integer> node, int key) {
        if (null == node) {
            return false;
        }
        if (node.data == key) {
            return true;
        }
        if (key > node.data) {
            return find(node.right, key);
        } else {
            return find(node.left, key);
        }
    }

    public void mid(TreeNode node) {
        if (node != null) {

            //左
            mid(node.left);
            //根
            System.out.println(node.data);
            //右
            mid(node.right);
        }
    }
}
